package basic.study.leetcode;

/**
 * @ClassName Mid240
 * @Description 搜索二维矩阵II
 * @Company inspur
 * @Author Kevin
 * @Date 2020/7/9 11:26
 * @Version 1.0
 */
public class Mid240 {
    class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
            if (matrix == null || matrix.length == 0) {
                return false;
            }

            int shortDim = Math.min(matrix.length, matrix[0].length);
            for (int i = 0; i < shortDim; i++) {
                boolean verticalFound = binarySearch(matrix, target, i, true);
                boolean horizontalFound = binarySearch(matrix, target, i, false);
                if (verticalFound || horizontalFound) {
                    return true;
                }
            }
            return false;
        }

        private boolean binarySearch(int[][] matrix, int target, int start, boolean vertical) {
            int lo = start;
            int hi = vertical?matrix[0].length-1:matrix.length-1;

            while (hi >= lo) {
                int mid = lo + (hi - lo)/2;
                if (vertical) {
                    if (matrix[start][mid] < target) {
                        lo = mid + 1;
                    } else if (matrix[start][mid] > target) {
                        hi = mid - 1;
                    } else {
                        return true;
                    }
                } else {
                    if (matrix[mid][start] < target) {
                        lo = mid + 1;
                    } else if (matrix[mid][start] > target) {
                        hi = mid -1;
                    } else {
                        return true;
                    }
                }
            }
            return false;
        }
    }
}
